#include <iostream>

using namespace std;

/*
*堆排序：建堆，排序
*非降序排序：先建立一个最大堆（左右孩子无需判断大小），
*          然后堆顶元素与最后叶子元素互换，
*          然后把最后叶子元素之前的元素调整成最大堆（无需考虑左右孩子大小），
*          最终，所有元素组成一个最小堆，非降序排序完成。
*建立最大堆：0.从最后一个非叶子节点开始.
*          1.判断该节点是否不小于其左右孩子，
*          2.若否则该元素与最大元素交换，继续判断被交换元素之后该节点为始是树是否组成最大堆。
*               若否，继续1步骤。
*          3. 若是则继续判断前一个非叶子节点，继续1步骤。
*/

//flag 为 未排序元素最后非叶子节点
int ajustHeap(int* data, int length, int flag)
{
   

    int curLeaf    = data[flag];
    int leftChild  = data[2*flag+1];
    int rightChild = data[2*flag+2];
    int maxIndex = -1;

    //该节点为叶子节点
    if (2*flag+1 >= length)
        return 1;
    
    //该节点为单叶子节点
    else if(2*flag+2 >= length)
    {
        if (curLeaf < leftChild)
            maxIndex = 2*flag+1;
        else
            return 1;
    }
    else
    {

        if (curLeaf >= leftChild && curLeaf >= rightChild)//本节点最大
            return 1;

        if (curLeaf < leftChild && leftChild >= rightChild)//左节点最大
            maxIndex = 2*flag+1;
        else
            maxIndex = 2*flag+2;
    }

    //swap
    data[flag] = data[maxIndex];
    data[maxIndex] = curLeaf;

    if (maxIndex > (length-1)/2)
        return 1;

    ajustHeap(data, length, maxIndex);

    return 1;
}

int buildHeap(int* data, int length)
{
    int i = 0;
    
    for (i = (length-1)/2; i>=0; i--)
    {
        ajustHeap(data, length, i);
    }

    return 1;
}

int sortHeap(int* data, int length)
{
    int i = 0;
    int unsortLength = length;
    int temp = 0;
    
    buildHeap(data, unsortLength);

    while (unsortLength > 0)
    {
        ajustHeap(data, unsortLength, 0);

        temp = data[0];
        data[0] = data[unsortLength-1];
        data[unsortLength-1] = temp;
        unsortLength--;
    }

    return 1;
}

int main()
{
    int data[100];
    int i = 0;

    srand(0);

    for (i = 0; i < 100; i++)
    {
        data[i] = rand();
    }

    cout<< "ori data: " <<endl;
    for (i = 0; i < 100; i++)
    {
        cout<< data[i] <<endl;
    }

    sortHeap(data, 100);

    cout<< "sort data: " <<endl;
    for (i = 0; i < 100; i++)
    {
        cout<< data[i] <<endl;
    }

    getchar();
    return 1;
}

